// 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
// k 是一个正整数，它的值小于或等于链表的长度。
// 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
// 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}

function reverse(a, b) {
  let pre = null
  let cur = a
  let nxt = a
  while (cur !== b) {
    nxt = cur.next
    cur.next = pre
    pre = cur
    cur = nxt
  }

  return pre
}


/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
  if (head === null) {
    return null
  }

  // 寻找间隔为 k 的区间 [a, b]
  let a = head
  let b = head
  for (let i = 0; i < k; i++) {
    if (b === null) {
      return head
    }
    b = b.next
  }

  // 翻转链表 [a, b] 部分
  let newHead = reverse(a, b)

  // 拼接链表
  a.next = reverseKGroup(b, k)

  return newHead
}